noip模拟赛2017.7.22

【试题概览】

题目名称 数7 正方形计数 速算游戏 单人纸牌
提交文件 seven.* count.* fun.* double.*
输入文件 seven.in count.in fun.in double.in
输出文件 seven.out count.out fun.out double.out
时间限制 1s 1s 1s 1s
空间限制 128MB 128MB 128MB 128MB

1. 数7

【题目描述】

1337 个人排成一个圈，从 1 号人开始报数，初始的方向是 1,2,3…。如果某个人报的数是 7 的倍数或 者数字中含有 7，那么报数的方向就反一下。问报数字 X 的是哪个人？

【输入格式】

一行一个数 X

【输出格式】

一行一个数表示最终报数字 X 的是哪个人。

【数据规模】

对于 30%的数据，满足 X<=10^6;
对于 90%的数据，满足 X<=10^8;
对于 100%的数据，满足 X<=10^9。

【输入样例】

1000

【输出样例】

1311

Solution

首先都想到了nlogn的做法，再想直接打表，如果打表的话估计也只能过10^8 ,而且还不稳定。先想想90分怎么做，考虑到主要的时间消耗在于对%7的判断以及对是否含有7的判断，与其取膜和分解判断，倒不如用个计数器和做类似于高精度加法（每次只加一复杂都有保证）.然后对于10^9只能间隔打表了。

2.正方形计数

【题目描述】

给定平面上 N 个点，你需要计算以其中 4 个点为顶点的正方形的个数。注意这里的正方形边不一定 需要和坐标轴平行。

【输入格式】

第一行一个数 N 以下 N 个点的坐标。

【输出格式】

一个数，表示正方形的个数

【数据规模】

对于 20%的数据，满足 1<=N<=20;
对于 100%的数据，满足 1<=N<=500，-50<=x[i],y[i]<=50，点不会重叠。

【输入样例】

7

0 0

0 1

1 0

1 1

1 2

2 1

2 2

Solution

暴力枚举正方形的四个顶点判断边是否相等即可。或者枚举两个定点根据条件判断另外两个点是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
struct node{
	int x,y;
	friend bool operator < (node a,node b){
		if(a.x==b.x)return a.y<b.y;
		return a.x<b.x;
	}
}point[550];
int n,ans;
int work(int x1,int y1,int x2,int y2){
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int main()
{
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&point[i].x,&point[i].y);
	sort(point+1,point+1+n);
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			int line_1=work(point[i].x,point[i].y,point[j].x,point[j].y);
			if(!line_1)continue;
			for(int k=j+1;k<=n;k++)
			{
				int line_2=work(point[i].x,point[i].y,point[k].x,point[k].y);
				if(line_1!=line_2)continue;
				for(int p=k+1;p<=n;p++)
				{
					int line_3=work(point[k].x,point[k].y,point[p].x,point[p].y);
					int line_4=work(point[p].x,point[p].y,point[j].x,point[j].y);
					int line_5=work(point[i].x,point[i].y,point[p].x,point[p].y);
					int line_6=work(point[j].x,point[j].y,point[k].x,point[k].y);
					if(line_2==line_3&&line_3==line_4&&line_5==line_6)
						ans++;
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}
/*
7
0 0
0 1
1 0
1 1
1 2
2 1
2 2
*/

【输出样例】

3

3.速算游戏

【题目描述】

jyx 和 cyy 打赌，比谁 24 点算得快，算得慢的那个人请客。24 点的规则是这样的：给定 4
个 1..9 的整数，用括号改变运算顺序，通过加、减、乘、除通的一系列运算，得到整数 24，
注意所有中间结果必须是整数（例如(22)/4 是允许的，而 2(2/4)是不允许的）。为了赢得
这个比赛，请写一个程序帮助我作弊，快速地计算出 24 点。

【输入格式】

一行 4 个整数，为给定的 4 个数字。输入数据保证有解。

【输出格式】

一行，以字符串的形式输出结果，注意将每一步的运算的括号补齐（例如(3+5)+6 和
3*(5+6)）如果有多种解答，输出字典顺序最小的一个。

【输入样例】

2357

【输出样例】

(((3*5)+2)+7)

Solution

被括号给骗了 感觉这道题挺蛮麻烦的，时只有3.5小时,所幸没有做，后来题时，真是傻逼题。太弱了…..括号在这题里只会有三种情况，自己想一想，然后依次写三个暴力就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define INF -2147483647
using namespace std;
int n[5],now[10],vis[10],r[50];
int num[50][5];
int cnt,tot;
char ans[50][100];
char trs(int x){
	if(x==1)return '+';
	if(x==2)return '-';
	if(x==3)return '*';
	if(x==4)return '/';
}
void Dfs_Pai(int pos){
	if(pos==5)
	{
		cnt++;
		for(int i=1;i<=4;i++)
			num[cnt][i]=now[i];
	}
	for(int i=1;i<=4;i++)
	{
		if(!vis[i])
		{
			now[pos]=n[i];
			vis[i]=true;
			Dfs_Pai(pos+1);
			vis[i]=false;
		}
	}
}
int calu(int a,int b,int opt)
{
	if(opt==1)return a+b;
	if(opt==2)return a-b;
	if(opt==3)return a*b;
	if(opt==4&&b!=0&&a%b==0)return a/b;
	return -INF;
}
void Dfs_Judge(int p)
{
	for(int i=1;i<=4;i++)
	{
		int result_1=calu(num[p][1],num[p][2],i);
 		if(result_1==-INF)continue;
		for(int j=1;j<=4;j++)
		{
			int result_2=calu(result_1,num[p][3],j);
			if(result_2==-INF)continue;
			for(int k=1;k<=4;k++)
			{
				int result=calu(result_2,num[p][4],k);
				if(result==24)
				{
					tot++;
					ans[tot][0]='(';
					ans[tot][1]='(';
					ans[tot][2]='(';
					ans[tot][3]=num[p][1]+'0';
					ans[tot][4]=trs(i);
					ans[tot][5]=num[p][2]+'0';
					ans[tot][6]=')';
					ans[tot][7]=trs(j);
					ans[tot][8]=num[p][3]+'0';
					ans[tot][9]=')';
					ans[tot][10]=trs(k);
					ans[tot][11]=num[p][4]+'0';
					ans[tot][12]=')';
				}
			}
		}
	}
	for(int i=1;i<=4;i++)
	{
		int result_1=calu(num[p][1],num[p][2],i);
		if(result_1==-INF)continue;
		for(int j=1;j<=4;j++)
		{
			int result_2=calu(num[p][3],num[p][4],j);
			if(result_2==-INF)continue;
			for(int k=1;k<=4;k++)
			{
				int result=calu(result_1,result_2,k);
				if(result==24)
				{
					tot++;
					ans[tot][0]='(';
					ans[tot][1]='(';
					ans[tot][2]=num[p][1]+'0';
					ans[tot][3]=trs(i);
					ans[tot][4]=num[p][2]+'0';
					ans[tot][5]=')';
					ans[tot][6]=trs(k);
					ans[tot][7]='(';
					ans[tot][8]=num[p][3]+'0';
					ans[tot][9]=trs(j);
					ans[tot][10]=num[p][4]+'0';
					ans[tot][11]=')';
					ans[tot][12]=')';
				}
			}
		}
	}
	for(int i=1;i<=4;i++)
	{
		int result_1=calu(num[p][3],num[p][4],i);
		if(result_1==-INF)continue;
		for(int j=1;j<=4;j++)
		{
			int result_2=calu(num[p][2],result_1,j);
			if(result_2==-INF)continue;
			for(int k=1;k<=4;k++)
			{
				int result=calu(num[p][1],result_2,k);
				if(result==24)
				{
					tot++;
					ans[tot][0]='(';
					ans[tot][1]=num[p][1]+'0';
					ans[tot][2]=trs(k);
					ans[tot][3]='(';
					ans[tot][4]=num[p][2]+'0';
					ans[tot][5]=trs(j);
					ans[tot][6]='(';
					ans[tot][7]=num[p][3]+'0';
					ans[tot][8]=trs(i);
					ans[tot][9]=num[p][4]+'0';
					ans[tot][10]=')';
					ans[tot][11]=')';
					ans[tot][12]=')';
				}
			}
		}
	}
}
bool cmp(int x,int y){
	for(int i=1;i<=13;i++)
	{
		if(ans[x][i]==ans[y][i])continue;
		return ans[x][i]<ans[y][i];
	}
}
int main()
{
	freopen("fun.in","r",stdin);
	freopen("fun.out","w",stdout);
	scanf("%d%d%d%d",&n[1],&n[2],&n[3],&n[4]);
	Dfs_Pai(1);
	for(int i=1;i<=cnt;i++)
		Dfs_Judge(i);
	for(int i=1;i<=tot;i++)
		r[i]=i;
	sort(r+1,r+1+tot,cmp);
	printf("%s",ans[r[1]]);
	return 0;
} 
/*
2 3 5 7
*/

4.单人纸牌

【题目描述】

单人纸牌游戏，共 36 张牌分成 9 叠，每叠 4 张牌面向上。每次，游戏者可以从某两个
不同的牌堆最顶上取出两张牌面相同的牌（如黑桃 10 和梅花 10）并且一起拿走。如果最
后所有纸牌都被取走，则游戏者就赢了，否则游戏者就输了。
George 很热衷于玩这个游戏，但是一旦有时有多种选择的方法，George 就不知道取
哪一种好了，George 会从中随机地选择一种走，例如：顶上的 9 张牌为 KS,KH,KD,9H,
8S,8D,7C,7D，6H，显然有 5 种取法： (KS,KH),(KS,KD),(KH,KD),(8S,
8D),(7C,7D)，当然 George 取到每一种取法的概率都是 1/5。
有一次，George 的朋友 Andrew 告诉他，这样做是很愚蠢的，不过 George 不相信，
他认为如此玩最后成功的概率是非常大的。请写一个程序帮助 George 证明他的结论：计
算按照他的策略，最后胜利的概率。

【输入格式】

9 行每行 4 组用空格分开的字串，每个字串两个字符，分别表示牌面和花色，按照从堆
底到堆顶的顺序给出。

【输出格式】

一行，最后胜利的概率，精确到小数点后 6 位。

【输入样例】

AS 9S 6C KS

JC QH AC KH

7S QD JD KD

QS TS JS 9H

6D TD AD 8S

QC TH KC 8D

8C 9D TC 7C

9C 7H JH 7D
8H 6S AH 6H

【输出样例】

0.589314

Solution

记忆化搜索轻松搞定，其实比较裸吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
char ch[10][5];
bool f[5][5][5][5][5][5][5][5][5];
double dp[5][5][5][5][5][5][5][5][5];
double dfs(int c1,int c2,int c3,int c4,int c5,int c6,int c7,int c8,int c9)
{
	if(f[c1][c2][c3][c4][c5][c6][c7][c8][c9])
		return dp[c1][c2][c3][c4][c5][c6][c7][c8][c9];
	f[c1][c2][c3][c4][c5][c6][c7][c8][c9]=true;
	int c[10];
	c[1]=c1;c[2]=c2;c[3]=c3;c[4]=c4;
	c[5]=c5;c[6]=c6;c[7]=c7;c[8]=c8;c[9]=c9;
	int sum=0;
	for(int i=1;i<=9;i++)
		for(int j=i+1;j<=9;j++)
		{
			if(ch[i][c[i]]==ch[j][c[j]]&&(c[i]>0)&&(c[j]>0))
			{	
				sum++;
				c[i]--;c[j]--;
				dp[c1][c2][c3][c4][c5][c6][c7][c8][c9]+=dfs(c[1],c[2],c[3],c[4],c[5],c[6],c[7],c[8],c[9]);
				c[i]++;c[j]++;
			}
		}
	if(sum!=0)
		dp[c1][c2][c3][c4][c5][c6][c7][c8][c9]/=sum;
	return dp[c1][c2][c3][c4][c5][c6][c7][c8][c9];
}
int main()
{
	freopen("double.in","r",stdin);
	freopen("double.out","w",stdout);
	for(int i=1;i<=9;i++)
		for(int j=1;j<=4;j++)
		{
			char a,b;
			cin>>a>>b;
			ch[i][j]=a;
		}
	f[0][0][0][0][0][0][0][0][0]=1;
	dp[0][0][0][0][0][0][0][0][0]=1;
	dp[4][4][4][4][4][4][4][4][4]=dfs(4,4,4,4,4,4,4,4,4);
	printf("%.6f",dp[4][4][4][4][4][4][4][4][4]); 
	return 0;
}
/*
AS 9S 6C KS
JC QH AC KH
7S QD JD KD
QS TS JS 9H
6D TD AD 8S
QC TH KC 8D
8C 9D TC 7C
9C 7H JH 7D
8H 6S AH 6H
*/

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:noip模拟赛2017.7.22

文章作者:Tyw_ei

发布时间:2017年07月23日 - 14时10分

最后更新:2017年07月24日 - 20时00分

原始链接:https://dextertyw.github.io/2017/07/23/[noip模拟赛2017.7.22]/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 【试题概览】
  2. 2. 1. 数7
    1. 2.1. 【题目描述】
    2. 2.2. 【输入格式】
    3. 2.3. 【输出格式】
    4. 2.4. 【数据规模】
    5. 2.5. 【输入样例】
    6. 2.6. 【输出样例】
  3. 3. Solution
  4. 4. 2.正方形计数
    1. 4.1. 【题目描述】
    2. 4.2. 【输入格式】
    3. 4.3. 【输出格式】
    4. 4.4. 【数据规模】
    5. 4.5. 【输入样例】
  5. 5. Solution
    1. 5.1. 【输出样例】
  6. 6. 3.速算游戏
    1. 6.1. 【题目描述】
    2. 6.2. 【输入格式】
    3. 6.3. 【输出格式】
    4. 6.4. 【输入样例】
    5. 6.5. 【输出样例】
  7. 7. Solution
  8. 8. 4.单人纸牌
    1. 8.1. 【题目描述】
    2. 8.2. 【输入格式】
    3. 8.3. 【输出格式】
    4. 8.4. 【输入样例】
    5. 8.5. 【输出样例】
  9. 9. Solution
,